package com.peng.leetcode.tree;

import java.util.Arrays;

/**
 * ConstructFromPrePost
 * 889. 根据前序和后序遍历构造二叉树
 * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
 *
 * @author: lupeng6
 * @create: 2023/3/26 20:44
 */
public class ConstructFromPrePost {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        if (preorder.length == 1) {
            return root;
        }
        int l = 0;
        for (int i = 0; i < preorder.length; i++) {
            if (preorder[1] == postorder[i]) {
                l = i + 1;
            }
        }
        root.left = constructFromPrePost(Arrays.copyOfRange(preorder, 1, l + 1),
                Arrays.copyOfRange(postorder, 0, l));
        root.right = constructFromPrePost(Arrays.copyOfRange(preorder, l + 1, preorder.length),
                Arrays.copyOfRange(postorder, l, postorder.length - 1));
        return root;
    }
}
